﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Drawing.Drawing2D;

namespace ComicsEditor
{
    public interface IShape
    {
        Point TopLeft { get; }

        bool Contains(Point p);

        int GetOutsideDir(Point p, int curDir);

        int GetOutsideCWDir(Point p, int curDir);

        int GetInsideDir(Point p, int curDir);

        int GetInsideCWDir(Point p, int curDir);

        object GetPosition(Point p);

        Point NextPoint(ref object position);

        Point PrevPoint(ref object position);
    }

    public class Contour : IShape
    {
        private Point[] points;
        private Point topLeft;
        private Dictionary<int, int[]> lines;
        private Dictionary<int, int[]> body;

        public Contour(Point[] points)
        {
            this.points = points;
            RebuildLines();
        }

        public Contour(IShape shape)
        {
            List<Point> contour = new List<Point>();
            Point p = shape.TopLeft;
            object pos = shape.GetPosition(p);
            while (true)
            {
                contour.Add(p);
                p = shape.NextPoint(ref pos);
                if (p == shape.TopLeft)
                    break;
            }

            points = contour.ToArray();
            RebuildLines();
        }

        public int Count
        {
            get
            {
                return points.Length;
            }
        }

        public Point this[int index]
        {
            get
            {
                return points[index];
            }
        }

        public void Translate(int dx, int dy)
        {
            for (int i = 0; i < points.Length; i++)
            {
                points[i].X += dx;
                points[i].Y += dy;
            }
            RebuildLines();
        }

        private void RebuildLines()
        {
            int i;

            int start = 0;
            topLeft = points[0];
            for (i = 1; i < points.Length; i++)
                if (topLeft.Y > points[i].Y || (topLeft.Y == points[i].Y && topLeft.X > points[i].X))
                {
                    topLeft = points[i];
                    start = i;
                }

            Dictionary<int, List<int>> intervals = new Dictionary<int, List<int>>();
            for (i = 0; i < points.Length; i++)
            {
                Point p = points[(start + i)%points.Length];
                Point p1 = points[(start + i + 1)%points.Length];
                Point p0 = points[(start + i + points.Length - 1)%points.Length];
                List<int> cur;
                if (!intervals.ContainsKey(p.Y))
                    intervals.Add(p.Y, cur = new List<int>());
                else
                    cur = intervals[p.Y];
                //bool closed = cur.Count == 0 || cur[cur.Count - 1] < 0;

                if (p0.Y < p.Y && p.Y > p1.Y)
                {
                    if (p0.X < p1.X)
                    {
                        cur.Add(p.X);
                        cur.Add(p.X);//end
                    }
                }

                if (p0.Y > p.Y && p.Y < p1.Y)
                {
                    if (p0.X > p1.X)
                    {
                        cur.Add(p.X);
                        cur.Add(p.X);//end
                    }
                }

                if (p0.Y > p.Y && p.Y > p1.Y)
                    cur.Add(p.X);//end

                if (p0.Y < p.Y && p.Y < p1.Y)
                    cur.Add(p.X);

                if (p0.Y > p.Y && p.Y == p1.Y)
                {
                    if (p.X > p1.X)
                        cur.Add(p.X);//end
                }

                if (p0.Y < p.Y && p.Y == p1.Y)
                {
                    if (p.X < p1.X)
                        cur.Add(p.X);
                }

                if (p0.Y == p.Y && p.Y > p1.Y)
                {
                    if (p0.X < p.X)
                        cur.Add(p.X);//end
                }

                if (p0.Y == p.Y && p.Y < p1.Y)
                {
                    if (p0.X > p.X)
                        cur.Add(p.X);
                }
            }

            lines = new Dictionary<int, int[]>();
            foreach (KeyValuePair<int, List<int>> pair in intervals)
            {
                /*int c1 = 0;
                int c2 = 0;
                for (i = 0; i < pair.Value.Count; i++)
                    if (pair.Value[i] < 0)
                    {
                        pair.Value[i] = -1 - pair.Value[i];
                        c2++;
                    }
                    else
                        c1++;
                if (c1 != c2)
                    throw new Exception();*/
                pair.Value.Sort();
                lines.Add(pair.Key, pair.Value.ToArray());
            }

            intervals.Clear();
            for (i = 0; i < points.Length; i++)
            {
                Point p = points[(start + i)%points.Length];
                Point p1 = points[(start + i + 1)%points.Length];
                Point p0 = points[(start + i + points.Length - 1)%points.Length];
                List<int> cur;
                if (!intervals.ContainsKey(p.Y))
                    intervals.Add(p.Y, cur = new List<int>());
                else
                    cur = intervals[p.Y];

                if (p0.Y < p.Y && p.Y > p1.Y)
                {
                    if (p0.X > p1.X)
                    {
                        cur.Add(-1 - p.X);
                        cur.Add(p.X);
                    }
                }

                if (p0.Y > p.Y && p.Y < p1.Y)
                {
                    if (p0.X < p1.X)
                    {
                        cur.Add(-1 - p.X);
                        cur.Add(p.X);
                    }
                }

                if (p0.Y > p.Y && p.Y > p1.Y)
                    cur.Add(-1 - p.X);

                if (p0.Y < p.Y && p.Y < p1.Y)
                    cur.Add(p.X);

                if (p0.Y > p.Y && p.Y == p1.Y)
                {
                    if (p.X < p1.X)
                        cur.Add(-1 - p.X);
                }

                if (p0.Y < p.Y && p.Y == p1.Y)
                {
                    if (p.X > p1.X)
                        cur.Add(p.X);
                }

                if (p0.Y == p.Y && p.Y > p1.Y)
                {
                    if (p0.X > p.X)
                        cur.Add(-1 - p.X);
                }

                if (p0.Y == p.Y && p.Y < p1.Y)
                {
                    if (p0.X < p.X)
                        cur.Add(p.X);
                }
            }

            body = new Dictionary<int, int[]>();
            foreach (KeyValuePair<int, List<int>> pair in intervals)
            {
                int c1 = 0;
                int c2 = 0;
                for (i = 0; i < pair.Value.Count; i++)
                    if (pair.Value[i] < 0)
                    {
                        pair.Value[i] = -1 - pair.Value[i];
                        c2++;
                    }
                    else
                        c1++;
                if (c1 != c2)
                    throw new Exception();
                pair.Value.Sort();
                body.Add(pair.Key, pair.Value.ToArray());
            }
        }

        public bool Contains(int x, int y)
        {
            if (lines.ContainsKey(y))
            {
                int[] line = lines[y];
                for (int i = 0; i < line.Length; i += 2)
                    if (x >= line[i] && x <= line[i + 1])
                        return true;
            }
            return false;
        }

        public bool ContainsBody(int x, int y)
        {
            if (body.ContainsKey(y))
            {
                int[] line = body[y];
                for (int i = 0; i < line.Length; i += 2)
                    if (x > line[i] && x < line[i + 1])
                        return true;
            }
            return false;
        }

        Point IShape.TopLeft
        {
            get
            {
                return topLeft;
            }
        }

        bool IShape.Contains(Point p)
        {
            return Contains(p.X, p.Y);
        }

        internal static Point[] Dirs = BalloonFillInstrument.Dirs;
        int IShape.GetOutsideDir(Point p, int curDir)
        {
            int i, j;
            for (j = 0; j < 8 && Contains(p.X + Dirs[(j + curDir)%8].X, p.Y + Dirs[(j + curDir)%8].Y); j++);
            for (i = j; i < 8 && !Contains(p.X + Dirs[(i + curDir)%8].X, p.Y + Dirs[(i + curDir)%8].Y); i++);
            if (i == 8 && j == 0)
                return -1;
            return (i + curDir)%8;
        }

        int IShape.GetOutsideCWDir(Point p, int curDir)
        {
            int i, j;
            for (j = 8; j > 0 && Contains(p.X + Dirs[(j + curDir)%8].X, p.Y + Dirs[(j + curDir)%8].Y); j--);
            for (i = j; i > 0 && !Contains(p.X + Dirs[(i + curDir)%8].X, p.Y + Dirs[(i + curDir)%8].Y); i--);
            if (i == 0 && j == 8)
                return -1;
            return (i + curDir)%8;
        }

        int IShape.GetInsideDir(Point p, int curDir)
        {
            int i, j;
            for (j = 0; j < 8 && !ContainsBody(p.X + Dirs[(j + curDir)%8].X, p.Y + Dirs[(j + curDir)%8].Y); j++);
            for (i = j; i < 8 && ContainsBody(p.X + Dirs[(i + curDir)%8].X, p.Y + Dirs[(i + curDir)%8].Y); i++);
            if (i == 8 && j == 0)
                return -1;
            return (i + curDir)%8;
        }

        int IShape.GetInsideCWDir(Point p, int curDir)
        {
            int i, j;
            for (j = 8; j > 0 && !ContainsBody(p.X + Dirs[(j + curDir)%8].X, p.Y + Dirs[(j + curDir)%8].Y); j--);
            for (i = j; i > 0 && ContainsBody(p.X + Dirs[(i + curDir)%8].X, p.Y + Dirs[(i + curDir)%8].Y); i--);
            if (i == 0 && j == 8)
                return -1;
            return (i + curDir)%8;
        }

        object IShape.GetPosition(Point p)
        {
            for (int i = 0; i < points.Length; i++)
                if (p.X == points[i].X && p.Y == points[i].Y)
                    return i;
            return null;
        }

        Point IShape.NextPoint(ref object position)
        {
            int i = (int)position;
            i++;
            position = i;
            return points[i%points.Length];
        }

        Point IShape.PrevPoint(ref object position)
        {
            int i = (int)position;
            i--;
            position = i;
            return points[(i + points.Length)%points.Length];
        }

        public bool Include(IShape shape)
        {
            bool included = false;

            IShape s1 = this;
            IShape s2 = shape;
            IShape st;
            Point topLeft = s1.TopLeft;
            if (topLeft.Y > s2.TopLeft.Y || (topLeft.Y == s2.TopLeft.Y && topLeft.X > s2.TopLeft.X))
            {
                st = s1;
                s1 = s2;
                s2 = st;
                topLeft = s1.TopLeft;
            }
            object pos = s1.GetPosition(topLeft);

            List<Point> contour = new List<Point>();
            Point cur = topLeft;
            int curDir = 0;
            while (true)
            {
                if (contour.Count > 1000000)
                    return false;
                contour.Add(cur);
                Point p1 = s1.NextPoint(ref pos);
                int d1;
                for (d1 = 0; d1 < 8 && (cur.X + Dirs[d1].X != p1.X || cur.Y + Dirs[d1].Y != p1.Y); d1++);
                int d2 = s2.GetOutsideDir(cur, curDir);
                if (d2 != -1 && (d2 - curDir + 7)%8 < (d1 - curDir + 7)%8)
                {
                    p1 = cur;
                    p1.X += Dirs[d2].X;
                    p1.Y += Dirs[d2].Y;
                    pos = s2.GetPosition(p1);
                    if (pos == null)
                        throw new Exception();
                    d1 = d2;
                    st = s1;
                    s1 = s2;
                    s2 = st;
                    included = true;
                }
                cur = p1;
                curDir = (d1 + 4)%8;
                if (cur == topLeft)
                    break;
            }

            if (included)
            {
                points = contour.ToArray();
                RebuildLines();
            }

            return included;
        }


        public bool Exclude(IShape shape)
        {
            bool excluded = false;

            IShape main = this;
            Point topLeft = main.TopLeft;
            object pos = main.GetPosition(topLeft);
            while (shape.Contains(topLeft))
            {
                topLeft = main.NextPoint(ref pos);
                if (topLeft == main.TopLeft)
                    return false;
            }

            List<Point> contour = new List<Point>();
            Point cur = topLeft;
            int curDir = -1;
            bool excluding = false;
            while (true)
            {
                if (contour.Count > 1000000)
                    return false;
                contour.Add(cur);
                Point p1;
                int d1;
                if (!excluding)
                {
                    p1 = main.NextPoint(ref pos);
                    for (d1 = 0; d1 < 8 && (cur.X + Dirs[d1].X != p1.X || cur.Y + Dirs[d1].Y != p1.Y); d1++);
                    int d2 = shape.GetOutsideCWDir(cur, curDir);
                    if (curDir < 0)
                        curDir = d2;
                    if (d2 != -1 && (d2 - curDir + 8)%8 > (d1 - curDir + 8)%8)
                    {
                        Point pt = cur;
                        pt.X += Dirs[d2].X;
                        pt.Y += Dirs[d2].Y;
                        if (ContainsBody(pt.X, pt.Y))
                        {
                            p1 = pt;
                            pos = shape.GetPosition(p1);
                            if (pos == null)
                                throw new Exception();
                            d1 = d2;
                            excluded = true;
                            excluding = true;
                        }
                    }
                }
                else
                {
                    p1 = shape.PrevPoint(ref pos);
                    for (d1 = 0; d1 < 8 && (cur.X + Dirs[d1].X != p1.X || cur.Y + Dirs[d1].Y != p1.Y); d1++);
                    int d2 = main.GetInsideCWDir(cur, curDir);
                    if (d2 != -1 && (d2 - curDir + 8)%8 > (d1 - curDir + 8)%8)
                    {
                        p1 = cur;
                        p1.X += Dirs[d2].X;
                        p1.Y += Dirs[d2].Y;
                        pos = main.GetPosition(p1);
                        if (pos == null)
                            throw new Exception();
                        d1 = d2;
                        excluding = false;
                    }
                }
                cur = p1;
                curDir = (d1 + 4)%8;
                if (cur == topLeft)
                    break;
            }

            if (excluded && contour.Count > 10)
            {
                points = contour.ToArray();
                RebuildLines();
            }

            return excluded;
        }
    }
}
